package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Queue;

/**
 *  加权无向图
 */
public class EdgeWeightedGraph {
    private final int V;            //记录顶点数量
    private int E;                  // 记录边数量
    private Queue<Edge>[] adj;            // 邻接表

    public EdgeWeightedGraph(int V){
        this.V=V;
        this.E=0;
        this.adj=new Queue[V];
        for (int i = 0; i <adj.length; i++) {
            adj[i]= new Queue<Edge>();
        }
    }
    /**
     * 获取图中顶点的数量
     * @return
     */
    public int V() {
        return V;
    }

    /**
     * 获取图中边的数量
     * @return
     */
    public int E(){
        return E;
    }

    /**
     * 向加权无向图中添加一条边e
     * @param e
     */
    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);
        adj[v].enqueue(e);
        adj[w].enqueue(e);
        E++;
    }

    /**
     * 获取和顶点v关联的所有边
     * @param v
     * @return
     */
    public Queue<Edge> adj(int v) {
        return adj[v];
    }

    /**
     * 获取加权无向图的所有边
     * @return
     */
    public Queue<Edge> edges(){
        Queue<Edge> allEdge = new Queue<>();
        for (int v = 0; v < V; v++) {
            for (Edge edge : adj[v]) {
                if (edge.other(v)<v){
                    allEdge.enqueue(edge);
                }
            }
        }
        return allEdge;
    }
}
